// Created by Sourabh Daptardar
#ifndef SDD_GRAPH_H
#define SDD_GRAPH_H

#include <iostream>
#include <map>
#include <iterator>
extern "C" {
#include <stdint.h>
}

using namespace std;

namespace ifl
{
	template< class I=int32_t, class W=int32_t >
		struct Edge
		{
			I u;
			I v;
			W weight;
			Edge(){}
			Edge(const I & _u, const I & _v, const W _w):u(_u),v(_v),weight(_w){}  
		};

	template< class I=int32_t, class W=int32_t >
		struct Graph
		{	
			int32_t V;
			int32_t E;
			bool isDirected;
			map<I,map< I,Edge<I,W> > > Adjlist;
			map<I,W> vweight;	

			Graph(const bool _isDirected=false):V(0),E(0),isDirected(_isDirected){}

			bool addEdge(const I &u,const I &v, const W w=1)
			{
				if( (Adjlist.find(u) == Adjlist.end()) || (Adjlist.find(v) == Adjlist.end())  ) return false;
				Adjlist[u][v] = Edge<I,W>(u,v,w);
				if( isDirected == false ) Adjlist[v][u] = Edge<I,W>(v,u,w); 
				E++;
				return true;
			}

			bool delEdge(const I &u, const I &v)
			{
				if( (Adjlist.find(u) == Adjlist.end()) || (Adjlist.find(v) == Adjlist.end())  ) return false;
				Adjlist[u].erase(v);
				if( isDirected == false ) Adjlist[v].erase(u);
				E--; 
				return true;	
			}


			bool addVertex(const I &id, const W vw=0)
			{
				if(Adjlist.find(id) != Adjlist.end() ) return false;
				map< I,Edge<I,W> > e;
				e.clear();
				Adjlist[id] = e;
				vweight[id] = vw;
				V++;	
				return true;
			}

			bool delVertex(const I &id)
			{ 
				if (Adjlist.find(id) == Adjlist.end()) return false; 
				int32_t sz = Adjlist[id].size();
				if( isDirected == false ) for( typename map< I,Edge<I,W> >::iterator itr = Adjlist[id].begin() ; itr != Adjlist[id].end() ; ++itr )  Adjlist[(itr->second).v].erase(id);
				else {
					typename map< I,map< I,Edge<I,W> > >::iterator itr1; 
					typename map< I,Edge<I,W> >::iterator itr2;

					for( itr1 = Adjlist.begin() ; itr1 != Adjlist.end() ; ++itr1 ) {
						for( itr2 = (itr1->second).begin() ; itr2 != (itr1->second).end() ;  ) {
							if( (itr2->second).v == id ) (itr1->second).erase(itr2++);
							else itr2++;
						}
					}


				}
				Adjlist[id].erase(Adjlist[id].begin(),Adjlist[id].end());	
				Adjlist.erase(id);
				vweight.erase(id);
				V--; E -= sz;
				return true;
			}


			ostream& print(ostream &out)
			{
				typename map< I,map< I,Edge<I,W> > >::iterator itr1; 
				typename map< I,Edge<I,W> >::iterator itr2;

				for( itr1 = Adjlist.begin() ; itr1 != Adjlist.end() ; ++itr1 ) {
					out << (itr1->first) << " :: ";
					for( itr2 = (itr1->second).begin() ; itr2 != (itr1->second).end() ; ++itr2 ) {
						out << (itr2->second).v << ":" << (itr2->second).weight << " ";	
					}
					out << endl;
				}

				return out;
			}



		};	




}

using namespace ifl;

#endif
